package 回溯

/*
https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked

79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
*/

func exist(board [][]byte, word string) bool {
	wordBytes := []byte(word)
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if dfs79(board, wordBytes, i, j, 0) {
				return true
			}
		}
	}
	return false
}

func dfs79(board [][]byte, word []byte, i, j, k int) bool {
	// 边界情况判断 行越界 列越界 矩阵元素已访问过
	if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != word[k] {
		return false
	}
	// 之前已经和目标字符串匹配成功了length-1个字符，此时又匹配成功了最后一个元素，直接返回结果
	if k == len(word)-1 {
		return true
	}
	// 标记当前矩阵元素，将其修改为特殊字符'#'，代表此元素已经访问过，防止之后搜索时重复访问
	temp := board[i][j]
	board[i][j] = '#'
	// 搜索元素的四个方向，上 左 下 右，匹配下一个目标元素
	res := dfs79(board, word, i, j-1, k+1) ||
		dfs79(board, word, i-1, j, k+1) ||
		dfs79(board, word, i, j+1, k+1) ||
		dfs79(board, word, i+1, j, k+1)
	board[i][j] = temp // 回退时还原当前矩阵元素
	return res         // 返回结果
}
